import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;



class Solution {
    List<List<String>> ret;
    List<String> list;
    boolean[] vis;
    boolean[] dig1;
    boolean[] dig2;


    public List<List<String>> solveNQueens(int n) {
        ret=new ArrayList<>();
        list=new ArrayList<>();
        vis=new boolean[n];
        dig1=new boolean[2*n];
        dig2=new boolean[2*n];

        backtrack(n,0);

        return ret;


    }


    private void backtrack(int n,int x){
        if(list.size()==n){
            ret.add(new ArrayList(list));
            return;
        }


        for(int i=0;i<n;i++){
            int d1=i+x;
            int d2=i-x;
            if(d2<0) d2=-d2+n;
            if(!vis[i]&&!dig1[d1]&&!dig2[d2]){
                char[] s=new char[n];
                Arrays.fill(s,'.');
                s[i]='Q';


                vis[i]=true;
                dig1[d1]=true;
                dig2[d2]=true;

                list.add(String.valueOf(s));
                backtrack(n,x+1);
                list.remove(list.size()-1);
                vis[i]=false;
                dig1[d1]=false;
                dig2[d2]=false;

            }

        }
    }
}


